package leetcode_800;

import java.util.Arrays;
import java.util.Stack;

/**
 *@author 周杨
 *LongestWordInDictionary_720 一个单词 是否由字典里的其他单词 一个个地拼起来 问最长单词
 *describe:前缀树深搜可以解决 或者排序字典 AC 26%
 *2018年10月11日 下午8:11:37
 */
public class LongestWordInDictionary_720 {
	public String longestWord(String[] words) {
		Arrays.sort(words);
	    int N = words.length;
	    String res = "";
	    Stack<String> stack = new Stack<>();
	    for (int i=0; i<N; i++) {
	        while (!stack.isEmpty() && stack.peek().length() >= words[i].length()) {
	            stack.pop();
	        }
	        String curr = stack.isEmpty() ? "" : stack.peek();
	        if (curr.length() + 1 == words[i].length() && words[i].startsWith(curr)) {
	            stack.push(words[i]);
	        }
	        if (!stack.isEmpty() && stack.peek().length() > res.length()) {
	            res = stack.peek();
	        }
	    }
	    return res;
    }
}
